package cc.willrock.algorithm.sort;

import java.util.Arrays;

public class QuickSort {

	public static int[] sort(int[] pData, int left, int right) {
		int i = left, j = right;
		int middle, strTemp;

		middle = pData[(left + right) / 2];
		do {
			while ((pData[i] < middle) && (i < right)) {
				i++;
			}

			while ((pData[j] > middle) && (j > left)) {
				j--;
			}

			if (i <= j) {
				strTemp = pData[i];
				pData[i] = pData[j];
				pData[j] = strTemp;
				i++;
				j--;
			}
		} while (i <= j);

		System.out.println(Arrays.toString(pData));
		if (left < j) {
			sort(pData, left, j);
		}

		if (right > i)
			sort(pData, i, right);
		return pData;
	}
	
	
	/*
	 * algorithm in a nutshell
	 * 
	 * 最好O(n*log(n))
	 * 平均O(n×log(n))
	 * 最坏O(n×n)
	 *  
	 */
	
	public static int[] sort2(int[] pData, int left, int right) {
		
		if (left < right) {
			int pi = partition(pData, left, right);
			System.out.println(Arrays.toString(pData));
			sort2(pData, left, pi - 1);
			sort2(pData, pi + 1, right);
		}
		return pData;
	}

	public static int partition(int[] pData, int left, int right) {
		// p = select pivot in A[left,right]
		int p = (left + right) / 2;
		// swap A[p] and A[right]
		int temp = pData[p];
		pData[p] = pData[right];
		pData[right] = temp;
		int store = left;

		for (int i = left; i < right; i++) {
			if (pData[i] < pData[right]) {
				temp = pData[i];
				pData[i] = pData[store];
				pData[store] = temp;
				store++;
			}
		}
		temp = pData[right];
		pData[right] = pData[store];
		pData[store] = temp;
		
		return store;
	}

	public static void main(String[] argv) {
	    //int[] a = {15,9,8,1,4,11,7,12,13,6,5,3,16,2,10,14};
		int[] a = { 5, 3, 1, 2, 4 };
		System.out.println(Arrays.toString(a));
		System.out.println(Arrays.toString(sort2(a, 0, a.length - 1)));

	}

}
